Structure and properties of large intersecting families
Abstract
We say that a family of -subsets of an -element set is intersecting, if any two of its sets intersect. In this paper we study different extremal properties of intersecting families, as well as the structure of large intersecting families. We also give some results on -uniform families without pairwise disjoint sets, related to Erdős Matching Conjecture.
We prove a conclusive version of Frankl’s theorem on intersecting families with bounded maximal degree. This theorem, along with its generalizations to cross-intersecting families, implies many results on the topic, obtained by Frankl, Frankl and Tokushige, Kupavskii and Zakharov and others.
We study the structure of large intersecting families, obtaining some general structural theorems which generalize the results of Han and Kohayakawa, as well as Kostochka and Mubayi.
We give degree and subset degree version of the Erdős–Ko–Rado and the Hilton–Milner theorems, extending the results of Huang and Zhao, and Frankl, Han, Huang and Zhao. We also extend the range in which the degree version of the Erdős Matching conjecture holds.
1 Introduction
Let and denote the power set of . For integers we put and for integers we denote the collection of all -element subsets (-sets) of . Any collection of sets we call a family. We call a family intersecting, if any two sets from it intersect. A “trivial” example of such family is all sets containing a fixed element. We call a family non-trivial, if not all of its sets contain the same element.
One of the oldest and most famous results in extremal combinatorics is the Erdős–Ko–Rado theorem:
Theorem 1 ([3]).
Let and consider an intersecting family . Then . Moreover, for the only families attaining this bound are the families of all -sets containing a given element.
Answering a question of Erdős, Ko, and Rado, Hilton and Milner [16] found the largest non-trivial intersecting family of -sets. Up to permutation of the ground sets, it is the family consisting of the set and all sets that contain and intersect . Such family has size , which is much smaller than provided is large as compared to .
This paper is mostly concerned with the properties of large intersecting families. It is separated in several relatively independent parts covering different topics. Below we give the summary of the topics covered and the structure of the paper.
-
Section 3:
In this section we give a conclusive version of the Frankl’s degree theorem (see Theorems 2, 3 in the next section). The main result gives the precise dependence of size of the family on (lower bound on) the number of sets not containing the most popular element. The result then is extended to cover the equality case, as well as the weighted case and the case of cross-intersecting families. It, in particular, strengthens the results of [5], [12], [24].
-
Section 4:
In this section we address the question, what is the structure of large intersecting families. Unlike in Section 3, where, due to the Kruskal-Katona theorem, we have to deal with lexicographical families only (for definitions and necessary results, see the next section), in this section we work with general families. We prove several results, which, in particular, cover a large part of results of [14], [20], and extend them much farther. One important advantage, as compared to the results of [20], is that the results do not require to be large w.r.t. .
- Section 5:
-
Section 6:
In this section we obtain an upper bound on the minimum degree of a family , which does not contain pairwise disjoint sets. The results extends the analogous result of [17] for large . The problem in question may be seen as a degree vesion of the Erdős Matching Conjecture.
Some of the results in Section 4 depend on the results from Section 5, while Section 6 is relatively independent from the previous two sections. Section 6 is completely independent.
In the next section we give some of the definitions and results crucial for the paper. In Section 7 we give some concluding remarks and state several open problems.
2 Preliminaries
The degree of an element is the number of sets from the family containing it. For a family the diversity is the quantity , where is the maximal degree of an element in . Below we discuss the connection between the diversity and the size of an intersecting family.
We will need the following result due to Kupavskii and Zakharov [24]. It is a slightly stronger version of Frankl’s result [5]:
Theorem 2 ([24]).
Let and be an intersecting family. Then, if for some real , then
| (1) |
The bound from Theorem 2 is sharp for integer , as witnessed by the example
We note that the case of Theorem 2 is precisely the Hilton-Milner theorem.
To allow the reader to compare Theorem 2 and the original Frankl’s theorem, let us state it here.
Theorem 3 ([5]).
Let and be an intersecting family. Then, if for some integer , then
We note that Theorem 3 is immediately implied by Theorem 2, while in the other direction it is not true, even for the integer values of .
One of the key ingredients in the proofs of several theorems is the Kruskal-Katona theorem. Below we state it in terms of lexicographical orderings. Let us first give some definitions. A lexicographical order (lex) on the sets from is an order, in which iff the minimal element of is smaller than the minimal element of . For let be the collection of largest sets with respect to lex.
We say that two families are cross-intersecting, if for any we have .
3 The complete diversity version of Frankl’s theorem
In this section we study in detail the relationship between the diversity of an intersecting family and its size. First, note that, if the value of diversity is given precisely, then it is very easy to determine the largest intersecting family with such diversity using Theorem 4. Studying the size of an intersecting family with given upper bounds on diversity is not interesting: in general, the smaller the diversity is, the larger families with such diversity exist.
In this section we obtain a strengthened version of Theorem 2, which will tell exactly, how large an intersecting family may be, given a lower bound on its diversity. We give all “extremal” values of diversity and the sizes of the corresponding families.
The difficulty to obtain such a version of Theorem 2 is that, while Theorem 4 gives a very strong and clear characterisation of families with fixed diversity, the size of the family is not monotone w.r.t. diversity (the size of the largest family with a given diversity does not necessarily decrease when diversity increases, although it is true in most cases), and an extra effort is needed to find the right point of view.
We will give two versions of the main theorem of this section. First, we give a “numerical” version with explicit sharp bounds on the size of an intersecting family. It may be more practical to apply in some cases, but it is difficult to grasp, what is hidden behind the binomial coefficients in the formulation. Thus, later in the section (and as an intermediate step of the proof), we will give a “conceptual” version of our main theorem. We note that the proof that we present is completely computation-free. In the later parts of this section we present strengthenings and generalisations of our main result. We will settle the equality case in Theorems 6, 7, as well as consider the weighted case and a generalization to the case of general cross-intersecting families.
We note that the main results of the section are meaningful for any .
The following representation of natural numbers is important for the (classic form of) the Kruskal-Katona theorem. Given positive integers and , one can always write down uniquely in the -cascade form:
For the sake of comparison, let us state the classical version of the Kruskal-Katona theorem (equivalent to Theorem 4).
To state our theorem, we need to represent the diversity of an intersecting family in a cascade form. Given a number , let us write it in the -cascade form in the following particular way:
where
Define and put . Note that and . We assume that , where .
We call a number resistant, if the following holds:
-
1.
, ;
-
2.
for each ;
-
3.
For convenience, we assume that is a resistant number.
Thus, in particular, any integer will have as one of the members in the -cascade form, so such is not resistant.
Let be all the resistant numbers. Put for convenience.
Theorem 6.
Let . Consider an intersecting family . Suppose that for and that the representation of in the -cascade form is
then
| (2) |
where and .
The expression in the right hand side of (2) strictly decreases as increases.
Moreover, the presented bound is sharp: for each there exists an intersecting family with diversity which achieves the bound in (2).
Let us first try to familiarize the reader with the statement of the theorem. We have for . Indeed, for we have . Thus, for any such we have and . Thus, the first condition of the definition of a resistant number is satisfied if . However, the second condition is only satisfied when , which is equivalent to (or when , ). From the discussion above we also get that for
Proposition 1.
Proof.
Let us first compare the statement of Theorem 6 with the statement of Theorem 2 for with integer . Such is resistant for any (note that is resistant due to the exceptional condition 3 in the definition). Moreover, it is not difficult to see that, if we substitute such in (2), then we will get the bound
which is exactly the bound (1). However, we are getting it here in more relaxed assumptions: while we know that this bound is sharp for , Theorem 6 also tells us that for the bound would be strictly worse (and provides us with a possibility to extract, how much worse). Moreover, even if , we are still getting the same upper bound.
Moving to the proof of the proposition, the function in the right hand side of (1) monotone decreasing as increases (and thus decreases). Therefore, to show that the bound (2) is stronger than (1), it is sufficient to show it for values , . But for each of these values the bound (2) is sharp, so (1) can be only weaker than (2) for these values.
As a matter of fact, we can replace the bound in (1) with any monotone decreasing function of , provided that the bound holds for each .
Finally, let us mention that we state Theorem 6 only for , since Theorem 2 already gives us the bound if , and we cannot get any better bound in this range. However, we are going to analyze the cases when the equality in the inequality for above can be attained. It is worth mentioning that the intersecting family attains the bound above on the cardinality, and has diversity . We also note that in a recent work [23] the author managed to prove that for with some constant independent of there are no intersecting families with diversity bigger than .
Our next goal is to state the “conceptual” version of Theorem 6. We will need certain preparations. We will use the framework and some of the ideas from [9], as well as from [24]. First of all, we pass to the cross-intersecting setting in a standard way: given an intersecting family , we consider two families
and, applying Theorem 4, from now on and until the end of the section assume that . Note that . For shorthand we denote . In the remaining part dedicated to Theorem 6 we will be mostly working with the set , in order not to confuse the reader and to keep clear the relationship between the diversity of intersecting families and the sizes of pairs of cross-intersecting families.
Both and are determined by their lexicographically last set. In this section we use lexicographical order on , which is defined as follows: iff or the minimal element of is smaller than the minimal element of . Let us recall some notions and results from [9] related to the Kruskal-Katona theorem and cross-intersecting families. For a set , and , we define
For example, the family is the same as the family for . If for a certain set , then we say that is the characteristic set of . Note that, for convenience, we assume that (motivated by the fact that is the characteristic set for the subfamily of all sets containing 1 in the original family), while .
We say that two sets and form a resistant pair, if the following holds. Assuming that the largest element of is , we have
-
1.
, ;
-
2.
for each we have (this condition, roughly speaking, says that in each there are more elements in than in );
-
3.
For convenience, we include the pair in the list of resistant pairs.
Note that 2 implies that for each resistant pair. There is a close relationship between this notion and the notion of a resistant number, which we discuss a bit later. Let us first give the “conceptual” characteristic set version of Theorem 6. For convenience, we put to correspond to the empty family.
Theorem 7.
Let . Consider all resistant pairs , where . Assume that . Then
| (3) |
and any cross-intersecting pair of families with satisfies
| (4) |
In terms of intersecting families, if is intersecting and , then .
First of all, we remark that the intersecting part is clearly equivalent to the second statement of the cross-intersecting part. Second, Proposition 2 below shows that the families and are cross-intersecting and thus (4) is sharp. Now let us deduce Theorem 6 from Theorem 7.
Reduction of Theorem 6 to Theorem 7.
For any set with the largest element we can compute the size of the family as follows. Find the first element , which is missing from , and consider the family with characteristic set . The size of this family is , since actually . Since , this family is a subfamily of . At each new step we find the next (not found yet) element , which is missing from , the set , and count the sets which belong to . Their number is precisely . But since we are stopping at every element that is not included in , we get that . Therefore, the last binomial coefficient is . At some point , and we stop the procedure, including the sets that satisfy . We get that
the -cascade form! Moreover, we know that the set is exactly the set from before the definition of a resistant number, and we have and thus .
Therefore, if is a resistant pair, then, representing in an -cascade form, we get that and . This immediately shows that and satisfy condition 1 of the definition of a resistant number. The implication in the other direction follows in the same way. Condition 2 of the definition of a resistant pair is equivalent to the statement that for each , which is, in turn, the same as saying . Finally, it is clear that correspond to the characteristic set .
We conclude that form a resistant pair if and only if is a resistant number. Doing calculations as above, one can conclude that
Before proving Theorem 7, let us first shed some light on pairs of cross-intersecting lexicographic families. We say that two sets and in strongly intersect, if there exists a positive integer , such that and . The following easy proposition was proven in [9]:
Proposition 2 ([9]).
Let and be subsets of , , and . Then and are cross-intersecting iff and strongly intersect.
We say that and form a maximal cross-intersecting pair, if whenever and are cross-intersecting with and , then necessarily and holds.
The following proposition from [9] is another important step in our analysis.
Proposition 3 ([9]).
Let and be positive integers, . Let and be non-empty subsets of with , . Suppose that and intersect strongly in their last element. That is, there exists , such that and . Then and form a maximal pair of cross-intersecting families.
Inversely, if and form a maximal pair of cross-intersecting families, then it is possible to find sets and such that , and satisfy the above condition.
We note that it may be helpful to interpret the strong intersection property, as well as the lexicographical order etc. in terms of -vectors: 1 on the -th position if is contained in the corresponding set, and otherwise.
Now we pass on to the proof of the cross-intersecting version of Theorem 7. Fix a cross-intersecting pair of families as in the theorem. There are three important reduction steps, which restrict the class of cross-intersecting families which we need to consider. First, as we have already mentioned, we assume that and for some characteristic sets . Second, in view of Proposition 3, we may assume that for some sets that strongly intersect in their last element. Note also that , so we do not have to worry about this condition in the propositions above.
Recall that we aim to maximize given a lower bound on . The third reduction step is the following lemma.
Lemma 1.
Consider a pair of cross-intersecting families . Suppose that for some sets , that strongly intersect in their last element .
Assume that and do not form a resistant pair, that is, there exists , such that . Put and choose so that it strongly intersects with in its largest element. Then the families with characteristic sets are cross-intersecting and satisfy and .
Moreover, if , then we may conclude that .
Proof of Lemma 1.
First, recall that . Since and are strongly intersecting, the families , are cross-intersecting. Next, clearly, and thus . Therefore, we only have to prove .
Consider the following families:
Most importantly, we have . Let us show, e.g., the first equality. We have , therefore . On the other hand, we claim that and are two consecutive sets in the lexicographic order on . Indeed, assume that the largest element of is . If , then , , which proves it in this case. If , then , . It is easy to see that the set that precedes in the lexicographic order on “replaces” with , that is, it is . Therefore,
which, together with the fact that and are disjoint, is equivalent to the equality we aimed to prove.
Next, consider a bipartite graph with parts and edges connecting disjoint sets. Then, due to the fact that and are cross-intersecting, is an independent set in .
The graph is biregular, and therefore the largest independent set in is one of its parts. We have , , where . By the condition from the lemma, we have , and, since , we have . We conclude that is the largest independent set in , so and therefore
If , then and is the unique independent set of maximal size in . Thus, we have strict inequality in the displayed formula above. ∎
Our next goal is to understand how do the resistant pairs behave. More specifically, we aim to show that (3) holds: that sizes of resistant cross-intersecting families are increasing as the size of the second family decreases.
Lemma 2.
Consider a resistant pair of cross-intersecting families , with characteristic sets , respectively, and another such resistant pair with characteristic sets . Assume also that .
If , then and .
Roughly speaking, while for general lexicographic pairs of families the size is not monotone w.r.t. the lexicographic order, it is monotone for resistant pairs, which are maximal with respect to the properties that interest us.
Remark that, since , then and thus must satisfy the second condition from the definition of a resistant pair. We also note that we do not use the property that form a resistant pair. The proof also works for .
The proof of this lemma is based on biregular bipartite graphs and is very similar to the proof of Lemma 1, although is a bit trickier.
Proof.
First of all, it is clear that in the conditions of the lemma we have . The rest of the proof is concerned with the inequality on the sums of sizes. We will consider two cases depending on how do the sets and relate.
Case 1. . Find the smallest , such that one of the sets contain , while the other does not. Since , we clearly have . Consider the set . Then we clearly have and . Accordingly, put to be , and consider the cross-intersecting families , which have characteristic vectors and , respectively. First, note that and is a resistant pair: it follows from the definition of . We claim that
We prove the inequality above as in Lemma 1, but the roles of and are now switched. Consider a bipartite graph with parts
and edges connecting disjoint sets. Similarly, we have . Indeed, let us verify, e.g., the second equality. All sets such that are in and in , as well as in , since . On the other hand, if we restrict to , the sets and are consecutive in the lexicographic order, and so any set from such that must satisfy . Therefore, and .
Since and are cross-intersecting, the set is independent in . On the other hand, the largest independent set in has size . Since the pair is resistant (and that is not the last element of ), we have that , which implies , and thus is the (unique) maximal independent set in . We have
and the desired inequality is proven. Therefore, when comparing and , we may replace with , or rather assume that . We have reduced Case 1 to the following case.
Case 2. . Arguing inductively, we may assume that , and that for some . Note that in that case is the last element of , and that . Consider a bipartite graph with parts
and edges connecting disjoint sets. As before, we have . Using the fact that , we again conclude that . ∎
Now let us put the things together.
Proof of Theorem 7.
First of all, (3) follows from Lemma 2. Next, given a pair of cross-intersecting families , we may assume using Proposition 3 that their characteristic sets strongly intersect in their last coordinate. Using Lemma 1, we may further replace them with a resistant pair with characteristic vectors , such that . Therefore, if and , then , and therefore the pair has at least as big sum of cardinalities as and . This completes the proof of the theorem.
We only have to add that, although do not satisfy the second requirement of the definition of a resistant pair, it does not pose any problems. We still may apply Lemma 2 to this pair. Moreover, if initially the characteristic set of the family satisfies , then, using Lemma 1 it would be eventually reduced to , and thus we may apply it as in other cases. ∎
Let us discuss some possible strengthenings and generalizations of Theorems 6 and 7. First of all, let us determine, for which , , it is possible to have equality in (4), given that are determined by a strongly intersecting pair of sets , , which intersect in their last element. We say that a pair of strongly intersecting sets as above is -neutral, if is obtained in the following recursive way:
-
1.
is -neutral;
-
2.
If is -neutral, then the set is -neutral, where .
In practice, this means that, starting from a set , we add the element and then continue adding every other element.
We remark that it is not difficult to see that any -neutral pair actually satisfies . Let us also note that : indeed, from the definition of a resistant pair, the largest element in is at most (actually, it is at most for all and equal to in the case ), and every newly added element (via part 2 of the recursive definition) is bigger by 2 than the previously added element.
Theorem 8.
Let . Consider a pair defined by strongly intersecting sets that intersect in their largest element. If for some , then equality in (4) holds if and only if the pair is -neutral.
Proof.
First, let us show that any -neutral pair would have equality in (4). We do it inductively. It is clear for a pair involving itself. Assuming it holds for , let us prove that it holds for .
Consider the pairs of cross-intersecting families , , corresponding to the -neutral pairs of sets and , respectively. Looking in the proof of Lemma 1, given that , the equality in occur if and only if, first , and, second, Indeed, in a connected biregular bipartite graph there are only two possible independent sets of maximal size: its parts.
Consider the set and the corresponding set . By the definition of a neutral set, we have
Therefore, applying the argument of Lemma 1 with
We get that , which implies . Moreover, since the sets and are consecutive in the lexicographical order on , and the same for . Therefore, .
In the other direction, take a set , , and its pair . Consider the corresponding pair of cross-intersecting families . Then it is easy to see that . (Otherwise, either , or must contain and thus precede some other resistant set, which precedes , and this would contradict the position of in the ordering.) Assuming that is the last element in , we must have
Indeed, otherwise, considering the bipartite graph with parts , as displayed above for that , we would get that and both and are non-empty. In this case , which means that the pair defined by the characteristic sets and its pair would satisfy . Moreover, , so and . This would contradict the equality in (4).
Therefore, since are not resistant, we have
(We cannot have “”, since otherwise we would have “” for .) Removing , we get a set , and conclude that . By induction on the size of the set , we may assume that is -neutral. But then is -neutral as well. ∎
A slight modification of this argument (with an extension of the definition of a neutral pair to the ones that start with ) gives the following:
Proposition 4.
Let . For any intersecting with we have .
Recall that there are intersecting families for both and that have size .
Next, our techniques allow us to give a weighted version of Theorems 6 and 7. Assume that, instead of maximising the expression with a given lower bound on , we are maximising the expression with some . (In terms of cross-intersecting families, we are maximising the expression .) Then the following is true.
Theorem 9.
Let . Consider all resistant pairs , where . Assume that . Put . Then
| (5) |
and any cross-intersecting pair of families with satisfies .
In terms of intersecting families, if is intersecting and , then .
Proof.
The proof of this theorem follows the same steps as the proof of Theorem 7. We sketch the proof of the cross-intersecting version of the theorem. Using Lemma 1, we may assume that and form a resistant pair (indeed, otherwise, replacing with which satisfy , definitely increases the value of ). Then, looking at the proof of Lemma 2, we see that in each of the cases the bipartite graph had parts of sizes , , where and . We also know that . Therefore, even if we put weight on each vertex of the part and weight 1 on each vertex of the part , we can still conclude that the independent set of the largest weight in is , and the rest of the argument works out as before. We have
| (6) |
Therefore, substituting as the weight in the part will work. ∎
Corollary 1.
Let . For any intersecting family , we have .
If, additionally, is non-trivial, then .
Is not difficult extend the considerations of this section to the case of cross-intersecting families , . The wording of Theorem 7 would stay practically the same. One just need to adjust the definition of a resistant pair. Note that, unlike before in this section, here we will work with cross-intersecting families on (and not ).
We say that two sets form an -resistant pair, if the following holds. Assuming that the largest element of is , we have
-
1.
, ;
-
2.
for each we have ;
-
3.
The pair is resistant.
Again, for convenience, we put to correspond to the empty family and to be an analogue of the set in this case, where is the number of resistant pairs. Here is the theorem, which is an analogue of Theorems 7, 8, 9 and Proposition 4 in the case of general cross-intersecting families. Its proof is a straightforward generalization of the proofs of the respective theorems, thus we omit it.
Theorem 10.
Let , . Consider all -resistant pairs , where . Assume that .
1. Then
| (7) |
and any cross-intersecting pair of families with satisfies
| (8) |
With an obvious generalization of the notion of a neutral pair, if the families , have characteristic sets , then we have equality in (8) if and only if is a -neutral pair.
2. The same conclusion could be made with , replaced with , , where is a constant,
3. Denote . For we have
For both , and the corresponding we have equality in the inequality above for , (note that the second family has cardinality and , respectively).
This theorem generalizes and strengthens many results on cross-intersecting families, in particular, the theorem for cross-intersecting families proven in [24] and the following theorem due to Frankl and Tokushige [12]
Theorem 11 (Frankl, Tokushige, [12]).
Let , , and suppose that families are cross-intersecting. Suppose that for some real number we have . Then
| (9) |
One easy corollary of ((7) and part 3 of) Theorem 10, which also appeared in [24] and other places, is as follows:
Corollary 2 ([24]).
Let , . Let be a pair of cross-intersecting families. Then, if , then
| (10) |
Moreover, the displayed inequality is strict unless .
If for , then
| (11) |
Moreover, if the left inequality on is strict, then the inequality in the displayed formula above is also strict.
Note that the values correspond to resistant pairs in Theorem 10.
4 Beyond Hilton-Milner theorem
Several authors aimed to determine precisely, what are the largest intersecting families in with certain restrictions. One of such questions was studied by Han and Kohayakawa, who determined precisely, what is the largest family of intersecting families that is neither contained in the Erdős-Ko-Rado family, nor in the Hilton-Milner family. In our terms, the question is simply as follows: what is the largest intersecting family with ? The proof of Han and Kohayakawa is quite technical and long. Kruskal-Katona-type arguments allow for a very short and simple proof in the case . For let us put
We note that and that are intersecting. Moreover, for and is the Hilton-Milner family.
Theorem 12 ([14]).
Let , . Then any intersecting family with satisfies
| (12) |
moreover, for the equality is attained only on the families isomorphic to .
We note that Han and Kohayakawa proved their theorem for , and also resolved the uniqueness case for . Unfortunately, this cannot be done in a simple way using our methods. A slightly weaker version of the theorem above (without uniqueness) is a consequence of one of the results obtained by Hilton and Milner [16] (see [14]).
It is not so difficult to deduce Theorem 12 from Theorem 4 directly, but using Theorems 6, 7 makes it even easier.
Proof.
In terms of Theorem 6, we know that for , and . Substituting for in (2), we get
which is exactly the right hand side of (12). We know that this is sharp, due to an example isomorphic to (it is also isomorphic to the corresponding example from Theorem 6).
Since the right hand side of (2) strictly decreases as increases, we may conclude that for any family with will have strict inequality in (2) with , and thus a strict inequality in (12). Moreover, for the lexicographic family with diversity has the same cardinality as , displayed above (due to Theorem 8, or via direct calculation), and no family with can have larger cardinality.
Therefore, the bound (12) is proven, and to complete the proof, we should only show that for among the intersecting families with all families achieving equality in (12) are isomorphic to . This could be done by a simple computation.
Any (maximal) intersecting family with is uniquely determined by the intersection of the two sets , which are not containing the most popular element, and thus is isomorphic to one of the , .
Using exclusion-inclusion formula for , we conclude that (the number of -sets that contain 1 and do not intersect either or ) (the number of sets that contain 1 and miss ) (the number of sets that contain 1 and miss ) (the number of sets that contain 1 and miss both and ) , and this function clearly strictly increases as the intersection size of and decreases, and so we “loose” more and more sets containing as become smaller. Therefore, the unique (up to isomorphism) maximal intersecting family with is . Theorem is proven. ∎
Let us denote the maximal intersecting family with . Note that is isomorphic to . It is not difficult to see that, in terms of Theorem 7, for we have and, therefore, (see the analysis after Theorem 7). We also have . Moreover, it is not difficult to see that for we have (indeed, we have for this range). Also, using Theorems 7 and 8 (or by direct calculation), we can conclude that .
The next theorem is another application of our method.
Theorem 13.
Assume that and . Consider an intersecting family , such that . Assume that . Then
| (13) |
with the equality only possible if is isomorphic to .
Note that is in a sense the family with the smallest among the ones that satisfy the condition of the theorem. Before we prove it, let us put it into context. The following theorem is one of the main results in [20]:
Theorem 14 ([20]).
Let and be sufficiently large. If is intersecting, and , then for .
Many results in extremal set theory are much easier to get once one assumes that is sufficiently large in comparison to . In this paper we prove the theorem above without the restriction on . It follows immediately from Theorem 13.
Theorem 15.
Let and . If is intersecting, and , then either is isomorphic to , or to a subset of for .
We note that for : e.g., taking is sufficient.
The following theorem is one of the main results of this paper. It generalizes Theorem 13 and gives a reasonable classification of all large intersecting families (actually, all families with not too large diversity). We prove it using yet another variation of our methods. Let us call a family typical minimal, if, first, for any we have , and, second, either or the number of elements contained in at least sets from is strictly bigger than . (Note that the first condition implies that there are at least elements contained in exactly sets from . Therefore, the second condition is, in particular, satisfied when .)
Theorem 16.
Assume that . Consider an intersecting family , such that . Assume that , where . Choose any and any typical minimal subfamily , such that . Take the (unique) maximal intersecting family , such that . Then, if or , we have
| (14) |
and equality is possible if and only if and is isomorphic to . In particular, in conditions above, if there are two sets in , such that for some , then
| (15) |
with the equality only possible if is isomorphic to .
We note that implies both and , which, in turn, implies due to Theorem 2. Therefore, in particular, all families of size bigger than that are covered by the theorem.
4.1 Proof of Theorem 13
We are not going to use Theorem 7, but rather give a self-contained proof in the spirit of the proofs in [24]. The proof is rather simple and consists of two important steps. The first is, via shifting and rearranging the elements, to reduce the family in question to a family that has certain structure (that is, sets of particular form). The second step is to use the method in the spirit of Lemmas 1, 2.
Let us first give the definitions related to shifting.
For a given pair of indices and a set define its -shift as follows. If or , then . If , then . That is, is obtained from by replacing with .
The -shift of a family is as follows:
We call a family shifted, if for all .
We note that shifts do not destroy the cross-intersecting property, therefore, any pair of cross-intersecting families may be transformed into a pair of shifted cross-intersecting families.
Take the family satisfying the requirements of the statement. If , then is isomorphic to one of the , , and we know that is the largest out of them. Therefore, we may assume that .
Consider the families . They are cross-intersecting. There are two cases to consider.
Case 1. Assume that we have two sets , such that .
First of all, by doing shifts, we may assume that there are two sets , such that . W.l.o.g., we may assume that , and that .
We have at least one more set in . Doing -shifts, where and , we can assume that . Apart from these elements, there are two more elements in , say, and , . Either , or , and we can do a -shift (or a -shift, if ), thus assuring that . Denote by the only remaining element of . Clearly, , since otherwise , and therefore we can safely do a -shift, thus transforming into and not changing . Moreover, if , then there is yet another set , which, in a similar way, we can transform into . In what follows, we assume that and
Assume first that and as above. Then we can use the following simple argument. Remove the set from , thus decreasing the sum of cardinalities of and by , and then add to all the -sets from the family
| (16) |
Clearly, each set from will intersect both and , and thus the pair will remain cross-intersecting. However, none of the sets from was present in before, since each set from is disjoint with . Therefore, we increase the sum of cardinalities of and by , which is more than for , . Therefore, the resulting cross-intersecting pair, which corresponds to the family , is bigger than the initial one.
If , then, due to the discussion two paragraphs above, we may assume that , , and that are shifted. Let be the lexicographically last element in . since the family is itself intersecting, for each set there must be an such that
| (17) |
because otherwise one of the sets in that may be obtained from by shifts will be disjoint from , but at the same time it will lie in .
Let us find the biggest such for and consider a bipartite graph with parts
and edges connecting disjoint sets. Then we see that, due to (17) and , . At the same time, is an independent set in and thus has size at most . Therefore, replacing with , , we do not decrease the sum of sizes. Moreover, it is easy to see that is intersecting (since ) and that are cross-intersecting. Indeed, any set in must intersect in a set which lexicographically precedes , and thus which intersects . Moreover, the family is shifted.
We repeat this with the lexicographically last element in , etc., until the lexicographically last set of the second family is . We note that we will arrive at such a moment. Indeed, the only obstacle is that we somehow remove from the second family due to the fact that , where was defined by some other set in the second family. Let us show that this is impossible. Recall that we chose as the largest index, for which the inequality (17) is satisfied. We must have . On the other hand, by the maximality of , we have . But for any .
Therefore, we may assume that is the lexicographically last element in . Thus, each , satisfies . The number of such sets is , and this, in particular, implies that . At the same time, , , since they all precede lexicographically (and thus could not have been removed before ).
Removing all the sets from apart from will decrease by at most . At the same time, we may add to the family as well as the following family:
| (18) |
We have , and both and are disjoint with , since . Thus we are getting new sets, and for . Therefore, we conclude that in this case as well, the size of the family is smaller than the size of .
Case 2. Assume that any two sets in intersect in at least elements. Then, knowing that , we may assume that (indeed, it is easy to check that all sets in must be contained in a certain -set). We may w.l.o.g. assume that the sets are contained in . Let us look at the sets that forbid in , as compared to the sets that are forbidden by . In both cases contain all sets intersecting , as well sets containing and one of . Apart from the one listed above, the sets allow only for sets that intersect in (their number is ), while the sets allow for the sets that contain , disjoint with , and intersect in at least one element (their number is ). Therefore, we can have sets more with than with . On the other hand, in this case for any . So we conclude that the families in this case are also smaller than .
4.2 Proof of Theorem 16
Choose , , , and satisfying the requirements of the theorem. We aim to prove that any family satisfying the requirements of the theorem has size strictly smaller than , unless it is isomorphic to . As a condition, in some of the cases we have . If it does not hold, but we have instead, then we still may assume that . Indeed, the largest family with diversity is at most as large as , and the latter family satisfies the requirements of the theorem (it contains a copy of any as in the statement). Therefore, if we show that is bigger than , it implies that is bigger than any family with diversity .
Therefore, from now on we assume that . Assume that (note that it may be empty). For each consider the following bipartite graph. The parts are
and edges connect disjoint sets. Note that , , where , . Due to the condition on , we have . Thus, we can apply (10) to
and conclude that . Therefore, removing from and adding sets from to , we get a pair of families with larger sum of cardinalities. Moreover, the new pair is cross-intersecting: all sets in contain , as well as the sets from .
Therefore, we may assume that all sets in contain .
Put . Due to minimality of , for each , , there is
We assume that , . In particular, .
Next, for each set consider the same bipartite graph as before. We can apply (11) with . Indeed, we know that since (note that for , since all of them contain due to the definition of ). Therefore, , and we may replace with and . The resulting family is cross-intersecting. Repeating this procedure, we may conclude that any set in not from must contain the set . If there are any other elements contained in all but 1 set from , we repeat the same procedure with them. Assume that they together with form a segment . Note that for each the set has the same size and must be non-empty. Otherwise, we have already proved the inequality (14), since the current is equal to .
Recall that is typical minimal, that is, the number of elements contained in at least 2 sets from is at least . If (which is the case, e.g., when ), then we proceed in the following way.
For each of size select one element for each . Note that may coincide. Put . Consider a bipartite graph with parts
and edges connecting disjoint sets. Note that , , and , , where , . In particular, . We have . Indeed, only the set may be left. Denote
We have , and, therefore, we may apply either (10) or (11) with (the upper bound on becomes trivial in that case) and conclude that either or . In both cases we may replace with and with all sets from that intersect the set from (if it is non-empty). As before, the size does not decrease and the cross-intersecting property is preserved.
Repeating this for all possible choices of and , we arrive at a point when any set from must intersect any set . Tt is clear that it only holds for a set if . But then , so , and the proof of (14) is complete in this case.
Assume now that . By the typical minimality of , we have an element , which is contained in at least 2 sets, say, and . We do something very similar to the previous case, but we have to be a bit more careful. We select a -set , which includes and , a set . It is clear that . Next, we consider the same bipartite graph as before. The sets in part now have size at least , while the sets in have size at most . Therefore, we can apply (10), (11) in the same way, and arrive at a family , such that any set in intersects any set of the form described above. In practice, this means that any set in contains ! Thus, we may now add to the set and proceed as in the first case: we now have at least common elements for all . The inequality (14) is proven.
5 Degree versions
Recently, Huang and Zhao [17] gave an elegant proof of the following theorem using a linear-algebraic approach:
Theorem 17 ([17]).
Let . Then any intersecting family has minimum degree at most .
The bound in the theorem is tight because of the trivial intersecting family, and the condition is necessary: in [17] the authors provide an example of a family for which has larger minimal degree. In fact, for most values of there are regular intersecting families in of maximal possible size: (see [18]). In the follow-up paper, Frankl, Han, Huang, and Zhao [8] proved
Theorem 18 ([8]).
Let and , where for , and for . Then any non-trivial intersecting family has minimum degree at most .
Several questions and problems arose in this context, that were asked in [17], [8], as well as in personal communication with Hao Huang and his presentation on the Recent Advances in Extremal Combinatorics Workshop at TSIMF, Sanya. Some of them are as follows:
-
1.
Can one find a combinatorial proof of Theorem 17? This question was partially answered by Frankl and Tokushige [13], who proved it under the additional assumption . Huang claims that their proof can be made to work for , provided that one applies their approach more carefully. However, the cases and remained open.
- 2.
- 3.
In this section we address these questions, partially answering all three of them. In the first theorem, we prove a -degree version of Theorem 17. Its proof is combinatorial and works, in particular, for and .
Theorem 19.
If , then for any intersecting family of -subsets of we have . More generally, if and , then .
In the second theorem we give a -degree version of Theorem 18 with much weaker restrictions on for large .
Theorem 20.
If , , and , or , , then for any non-trivial intersecting family of -subsets of we have .
After writing a preliminary version of the paper, we read the paper [13], where Theorem 19 is proven for and . It turned out that the approach the authors took is very similar to the approach we use to prove Theorem 19. However, it seems that their proof, unlike ours, does not work for , which is probably due to the fact that they use the original Frankl’s degree theorem (see Section 2).
5.1 Calculations
In this section we do some of the calculations used in the proofs of Theorems 19 and 20. Note that, substituting in (1), we get that
| (19) |
We also have
Clearly, for the last expression is maximized for , and we get the following bound, provided :
| (20) |
If , then we get that the ratio is at least .
We will also use the following formula:
| (21) |
5.2 Proof of Theorem 19
Take an intersecting family with maximum degree and diversity . Then, by definition, . W.l.o.g., we suppose that the element has the largest degree.
Proposition 5.
Fix some . If for an intersecting family of -sets with maximum degree and diversity we have
| (22) |
then .
Proof.
The sum of -degrees of all -subsets of is Therefore, there is a -tuple of elements in , such that
| (23) |
The ratio of two fractions is
Therefore, if (22) holds, then
| (24) |
∎
To prove Theorem 19, we are only left to verify (22) for all intersecting families. It is vacuously true for trivial intersecting families, so we may assume that . Fix as in the theorem. We have two cases to distinguish.
Case 1. . We only need to show that (1) holds. We may apply Corollary 1 (otherwise, it is not difficult to obtain via direct calculations). We only have to check that
| (25) |
Putting , where , we see that, if , then (25) holds for any . If , then we must have
which is satisfied when
Case 2. . By the calculations in Section 5.1, We know that , and we use the following easy bound on
| (26) |
Thus, it is sufficient for us to check that the following inequality holds:
If , then it simplifies to , which holds for any .
If , then it simplifies to a quadratic inequality in , which holds for
The right hand side is at most
5.3 Proof of Theorem 20
The strategy of the proof is very similar to that of Theorem 19. Fix a non-trivial intersecting family with (otherwise, it is a subfamily of some Hilton-Milner family). W.l.o.g., suppose that the element of the family with maximal degree is 1, and that contains the set . Then any other set containing must intersect . We compare with the Hilton-Milner family We consider cases depending on .
The case analysis, however, will be more complicated, as compared to the previous case. Notably, we get a new non-trivial Case 1.
Case 1. . We have , and we may apply Theorem 4 to the families and . We get that the cardinality of is at most the cardinality of all -subsets of that intersect the sets and . In other words, the degree of is at most . That is, some sets from containing are missing from .
Denote . By the paragraph above, we have . Consider a subfamily , such that each intersects in at least elements.
Then, denoting by the Hilton-Milner family, it is easy to see that the following rough estimate holds.
| (29) |
Indeed, the first summand is the average loss in the -degree of -sets in , and each set contributing to can contribute at most 1 to minimum -degree. In the rest of this case our goal is to show that the RHS in (29) is always positive.
Let us first estimate the size of . To do so, we have to exclude all the sets that intersect in more than elements. Since is always in the set, the number of sets we have to exclude is
We have for any , since . Therefore, the sum above is at most
and we have
| (30) |
To show that the RHS in (29) is always positive and thus to conclude the proof in Case 1, it is sufficient to show the first in the following chain of inequalities:
| (31) |
Note that the second inequality is just a corollary of Newton’s binom and the fact that . We also use the fact that .
If , , then in the worst case for (31) is , and the first inequality in (31) transforms into
which holds for .
If , , then we have
where the last inequality holds for any . On the other hand, using the above conditions on , we have
Comparing this chain of inequalities with the one above, we conclude that for our choice of parameters
Statement 1.
Fix some . If for an intersecting family of -sets with maximum degree and diversity we have
| (32) |
then .
We apply (1). Our situation corresponds to the case . To verify (32), one has to check that
| (33) |
We have
The last expression is minimized when . Comparing the product above with the product in (33), we get
Therefore, to prove (33), it is sufficient for us to show that
| (34) |
For the fraction in the left hand side, we use the following property: if we add 1 to one of the multiples in the numerator and 1 to one of the multiples in the denominator, then the fraction will only increase, and the expression in the left hand side will decrease. If , then the LHS of (34) is
and therefore (33) is satisfied for any and .
| (35) |
holds.
If , then it simplifies to
This is equivalent to
| (37) |
The right hand side is at most
Therefore (37) follows from
which holds for any and
If , then
where in the inequality (*) we used the fact that the difference between the first numerator and the second numerator multiplied by by is , which is positive for ; in the last inequality we used that . On the other hand,
Therefore, combining these calculations, the inequality (36) would follow from the inequality
| (38) |
If , then the right hand side of the inequality above is at most while the left hand side is at least . It is easy to see that, say, for , .
To conclude, we remark that the only conditions on that we used for were and . The later one is implied by the former one.
6 Degree version of the Erdős Matching Conjecture
The matching number of a family is the maximum number of pairwise disjoint sets from . That is, intersecting families are exactly the families with matching number one. It is a natural question to ask, what is the largest family with matching number (at most) . Speaking of uniform families, let us denote the size of the largest family with . Note that this question is only interesting when . The following two families are the natural candidates:
Erdős conjectured [2] that . This conjecture is known as the Erős Matching conjecture. It was studied quite extensively over the last 50 years, but it remains unsolved in general. It is known to be true for [7] and for [6]. We note that is bigger than already for relatively small : the condition should suffice.
A degree version of Erdős Matching Conjecture and related problems attracted a lot of attention recently (see, e.g., [15], [22]). The following theorem was proved in [17].
Theorem 21 ([17]).
Given with , if for a family with we have .
This improved the result of Bollobás, Daykin, and Erdős [1], who arrived at the same conclusion for . The authors conjectured that the same should hold for any . Note that in the degree version we do not include the family , since its minimum -degree is 0 for and . Note that, for general we have .
In this paper we improve and generalize Theorem 21 above result for large in comparison to .
Theorem 22.
Fix and , such that , and ( for ). For any family with we have , with equality only in the case .
We note that the constants in the proof are not optimal, and chosen in this way to simplify the calculations. In the proof we make use of the stability theorem, proved by the author together with P. Frankl [10, 11]. Recall that is the minimal size of a set , such that for any . For fixed , saying that satisfies and is equivalent to saying that is not isomorphic to a subfamily of .
Theorem 23 ([10]).
Let . Then for any family with and we have
| (39) |
Proof of Theorem 22.
We prove the theorem by contradiction. Fix and take a family with . It cannot be a subfamily of since . Therefore, and, assuming that , we conclude that satisfies (39). By simple double counting, we have
Note that and . We have
We have It is not difficult to verify that for one has . Therefore, assuming that
| (40) |
we have
| (41) |
On the other hand, we have and , and
provided
| (42) |
We conclude that, provided that (40) and (42) hold, we get
which is nonnegative provided . This inequality holds for and . The last inequality is satisfied for , since then . We note that with this choice of and both (40) and (42) hold.
For one may improve (41) to and the condition on may be relaxed to . The equality part of the statement follows easily from the fact that strict inequality is obtained in the case when . ∎
7 Conclusion
In this paper we explored several question concerning intersecting families. Some of these questions remain only partially resolved, and it would be highly desirable to settle them.
First of all, it would be desirable to understand the structure of families with diversity larger than . As shown in [23], no such family exist for with some absolute constant . It is believed to be true for . For , however, we do have such families, and both the proof of the conjecture above and the understanding of their structure is interesting on its own and would be helpful in different questions (for more information, see [23]).
In this paper we have applied the machinery of Section 3, based on papers [9], [24], to the setting of general families (see Theorem 16). This gave a reasonable classification of all large intersecting families. However, it is by no means complete.
Problem 1.
To what extent one could relax the condition on diversity and/or on in Theorem 16?
Problem 2.
In terms of Theorem 16, is there a reasonable way to compare the sizes of intersecting families generated by typical minimal families? In particular, we believe that, if contains a typical minimal subfamily , such that , then
| (43) |
with equality only possible if is isomorphic to .
We believe that Theorem 16 is an important step towards classification of families with large covering numbers (the size of the smallest subset that intersects any set from ). An important result in this direction we obtained by Frankl [4], who resolved this problem for and, again, for large enough .
Problem 3.
Extend Theorem 16 to families with .
The next question concerns the degree version of the Hilton-Minler theorem.
Problem 4.
Is there an example for (, is a small constant), such that there exists a non-trivial intersecting family with minimal -degree (-degree) higher than that of the Hilton-Milner family?
One reason to believe that the answer to this question is positive is that the degrees of elements in the Hilton-Milner family are irregular, even if we exclude the element of the highest degree out of consideration.
Finally, the following question concerning cross-intersecting families seem interesting for us.
Problem 5.
Consider two cross-intersecting families that are disjoint. Is it true that
References
- [1] B. Bollobás, D.E. Daykin, P. Erdős, Sets of independent edges of a hypergraph, Quart. J. Math. Oxford Ser. 27 (1976), N2, 25–32.
- [2] P. Erdős, A problem on independent r-tuples, Ann. Univ. Sci. Budapest. 8 (1965) 93–95.
- [3] P. Erdős, C. Ko, R. Rado, Intersection theorems for systems of finite sets, The Quarterly Journal of Mathematics, 12 (1961) N1, 313–320.
- [4] P. Frankl, On intersecting families of finite sets, Bull. Austral. Math. Soc. 21 (1980), 363– 372.
- [5] P. Frankl, Erdos-Ko-Rado theorem with conditions on the maximal degree, Journal of Combinatorial Theory, Series A 46 (1987), N2, 252–263.
- [6] P. Frankl, Improved bounds for Erdős’ Matching Conjecture, Journ. of Comb. Theory Ser. A 120 (2013), 1068–1072.
- [7] P. Frankl, On the maximum number of edges in a hypergraph with given matching number, Discrete Applied Mathematics 216 (2017), 562–581.
- [8] P. Frankl, J. Han, H. Huang, Y. Zhao A degree version of Hilton-Milner theorem, arXiv:1703.03896v2
- [9] P. Frankl, A. Kupavskii, Erdős-Ko-Rado theorem for -vectors, arXiv:1510.03912
- [10] P. Frankl, A. Kupavskii, Families with no pairwise disjoint sets, Journal of London Mathematical Society (2017), arXiv:1607.06122
- [11] P. Frankl, A. Kupavskii, Two problems of P. Erdős on matchings in set families, submitted, arXiv:1607.06126
- [12] P. Frankl, N. Tokushige, Some best possible inequalities concerning cross-intersecting families, Journal of Combinatorial Theory, Series A 61 (1992), N1, 87–97.
- [13] P. Frankl, N. Tokushige, A note on Huang–Zhao theorem on intersecting families with large minimum degree, Discrete Mathematics 340 (2016), N5, 1098–1103.
- [14] J. Han, Y. Kohayakawa, The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton–Milner family, Proc. Amer. Math. Soc. 145 (2017) N1, 73–87.
- [15] H. Hán, Y. Person, M. Schacht, On perfect matchings in uniform hypergraphs with large minimum vertex degree, SIAM Journal on Discrete Mathematics 23 (2009), N2, 732–748.
- [16] A.J.W. Hilton, E.C. Milner, Some intersection theorems for systems of finite sets, Quart. J. Math. Oxford 18 (1967), 369–384.
- [17] H. Huang and Y. Zhao, Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture, J. Combin. Theory Ser. A, to appear
- [18] F. Ihringer, A. Kupavskii, Regular intersecting families, preprint.
- [19] G. Katona, A theorem of finite sets, “Theory of Graphs, Proc. Coll. Tihany, 1966”, Akad, Kiado, Budapest, 1968; Classic Papers in Combinatorics (1987), 381-401.
- [20] A. Kostochka, Dhruv Mubayi, The structure of large intersecting families Proc. Amer. Math. Soc. 145 (2017), N6, 2311–2321.
- [21] J.B. Kruskal, The Number of Simplices in a Complex, Mathematical optimization techniques 251 (1963), 251-278.
- [22] D. Kühn, D. Osthus, Embedding large subgraphs into dense graphs, Surveys in combinatorics (2009). Papers from the 22nd British combinatorial conference, St. Andrews, UK, July 5–10, 2009, pages 137–167.
- [23] A. Kupavskii, Diversity of intersecting families, submitted
- [24] A. Kupavskii, D. Zakharov, Regular bipartite graphs and intersecting families, arXiv:1611.03129